package com.rran.study.algorithm.easy.day08;

import com.rran.study.algorithm.medium.day06.ListNode;

import java.util.Stack;

/**
 * @author yy
 * @Type Solution.java
 * @Desc 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
 * <p>
 * 示例：
 * <p>
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 * <p>
 * 输入：1->2->4, 3->5->6
 * 输出：1->2->3->4->5->6
 * <p>
 * 输入：4->5->6, 1->2->3
 * 输出：1->2->3->4>5->6
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2020/9/9
 */
public class Solution {

    public static void main(String[] args) {
        ListNode l1 = new ListNode(4);
        ListNode l2 = new ListNode(5);
        ListNode l3 = new ListNode(6);
        ListNode l4 = new ListNode(1);
        ListNode l5 = new ListNode(2);
        ListNode l6 = new ListNode(3);
        l1.setNext(l2);
        l2.setNext(l3);
        l4.setNext(l5);
        l5.setNext(l6);
        Solution solution = new Solution();
        ListNode result = solution.mergeTwoLists(l1, l4);
        result.printListNode(result);
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.getVal() < l2.getVal()) {
                cur.setNext(l1);
                cur = cur.getNext();
                l1 = l1.getNext();
            } else {
                cur.setNext(l2);
                cur = cur.getNext();
                l2 = l2.getNext();
            }
        }
        // 任一为空，直接连接另一条链表
        if (l1 == null) {
            cur.setNext(l2);
        } else {
            cur.setNext(l1);
        }
        return dummyHead.getNext();
    }
}
